﻿


//博客： 位运算 所用例题
//博客链接：https://blog.csdn.net/weixin_64099089/article/details/150017224?sharetype=blogdetail&sharerId=150017224&sharerefer=PC&sharesource=weixin_64099089&spm=1011.2480.3001.8118

//https://leetcode.cn/problems/is-unique-lcci/
//
//面试题 01.01.判定字符是否唯一
//实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
//
//示例 1：
//
//输入 : s = "leetcode"
//输出 : false
//示例 2：
//
//输入 : s = "abc"
//输出 : true
//限制：
//
//0 <= len(s) <= 100
//s[i]仅包含小写字母
//如果你不使用额外的数据结构，会很加分。

//class Solution {
//public:
//    bool isUnique(string astr) {
//        bitset<26> bs;
//        if (astr.size() > 26) return false;
//        for (auto ch : astr) {
//            if (bs.test(ch - 'a')) return false;
//            bs.set(ch - 'a');
//        }
//        return true;
//    }
//};

//https://leetcode.cn/problems/missing-number/
//
//268. 丢失的数字
//给定一个包含[0, n] 中 n 个数的数组 nums ，找出[0, n] 这个范围内没有出现在数组中的那个数。
//
//
//
//示例 1：
//
//输入：nums = [3, 0, 1]
//
//输出：2
//
//解释：n = 3，因为有 3 个数字，所以所有的数字都在范围[0, 3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
//
//示例 2：
//
//输入：nums = [0, 1]
//
//输出：2
//
//解释：n = 2，因为有 2 个数字，所以所有的数字都在范围[0, 2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
//
//示例 3：
//
//输入：nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
//
//输出：8
//
//解释：n = 9，因为有 9 个数字，所以所有的数字都在范围[0, 9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
//
//提示：
//
//n == nums.length
//1 <= n <= 104
//0 <= nums[i] <= n
//nums 中的所有数字都 独一无二
//
//
//进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题 ?
//
//class Solution {
//public:
//    int missingNumber(vector<int>& nums) {
//        int n = nums.size(), res = 0;
//        for (int i = 0; i < n; ++i) {
//            res ^= i;
//            res ^= nums[i];
//        }
//        res ^= n;
//        return res;
//    }
//};
//
//https://leetcode.cn/problems/sum-of-two-integers/
//371. 两整数之和
//给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。
//
//
//
//示例 1：
//
//输入：a = 1, b = 2
//输出：3
//示例 2：
//
//输入：a = 2, b = 3
//输出：5
//
//
//提示：
//
//- 1000 <= a, b <= 1000

//class Solution {
//public:
//    int getSum(int a, int b) {
//        int add = (a & b) << 1, res = a ^ b; //保存进位
//        b = add;
//        while (add) {
//            add = (res & b) << 1;
//            res ^= b;
//            b = add;
//        }
//        return res;
//    }
//};
//
//
//https://leetcode.cn/problems/single-number-ii/
//137. 只出现一次的数字 II
//给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
//
//你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
//
//
//
//示例 1：
//
//输入：nums = [2, 2, 3, 2]
//输出：3
//示例 2：
//
//输入：nums = [0, 1, 0, 1, 0, 1, 99]
//输出：99

//
//提示：
//
//1 <= nums.length <= 3 * 104
//- 231 <= nums[i] <= 231 - 1
//nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
//
//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        //统计每一个比特位出现的次数
//        vector<int> cnt(32);
//        for (auto e : nums) {
//            for (int i = 0; i < 32; ++i) {
//                if ((e >> i) & 1) cnt[i]++;
//            }
//        }
//        int res = 0;
//        for (int i = 0; i < 32; ++i) {
//            if (cnt[i] % 3) res |= (1 << i);
//        }
//        return res;
//    }
//};

//https://leetcode.cn/problems/missing-two-lcci/
//面试题 17.19.消失的两个数字
//给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
//
//以任意顺序返回这两个数字均可。
//
//示例 1：
//
//输入：[1]
//输出：[2, 3]
//示例 2：
//
//输入：[2, 3]
//输出：[1, 4]
//提示：
//
//nums.length <= 30000

//class Solution {
//public:
//    vector<int> missingTwo(vector<int>& nums) {
//        int tmp = 0, i = 0, N = nums.size() + 2;
//        for (int x = 1; x <= N; ++x) tmp ^= x;
//        for (auto e : nums) tmp ^= e;
//        //找出不同的一位
//        while (1) {
//            if ((tmp >> i) & 1) break; //说明第i位不同
//            else ++i;
//        }
//        //按照第i位是否为1分成两组进行异或运算
//        int res1 = 0, res2 = 0;
//        for (int x = 1; x <= N; ++x) {
//            if ((x >> i) & 1) res1 ^= x;
//            else res2 ^= x;
//        }
//        for (int x : nums) {
//            if ((x >> i) & 1) res1 ^= x;
//            else res2 ^= x;
//        }
//        return { res1,res2 };
//    }
//};

